package dynamic_programming;
//https://leetcode.cn/problems/qJnOS7/description/
public class LCR_095最长公共子序列 {
    //二维动态规划
    class Solution {
        public int longestCommonSubsequence(String text1, String text2) {
            int m = text1.length(), n = text2.length();
            int[][] dp = new int[m+1][n+1];
            for(int i=1; i<=m; i++){
                char c1 = text1.charAt(i-1);
                for(int j = 1; j <= n; j++){
                    char c2 = text2.charAt(j-1);
                    if(c1 == c2){
                        dp[i][j] = dp[i-1][j-1] + 1;
                    }else
                        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
            return dp[m][n];
        }
    }
    //1:1 翻译成递推
    class Solution2 {
        public int longestCommonSubsequence(String text1, String text2) {
            char[] s = text1.toCharArray(), t = text2.toCharArray();
            int m = s.length, n = t.length;
            int[][] dp = new int[m+1][n+1];
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    dp[i+1][j+1] = s[i] == t[j] ? dp[i][j] + 1 :
                            Math.max(dp[i+1][j],dp[i][j+1]);
                }
            }
            return dp[m][n];
        }
    }
}
